#pragma once

#include <vector>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr) { }
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) { }
};

class Solution
{
public:
    std::vector<int> postorderTraversal(TreeNode* root)
    {
        std::vector<int> visited;
        traverse_postorder(root, visited);
        return visited;
    }

    std::vector<int> postorderTraversal2(TreeNode* root)
    {
        std::vector<int> visited;
        std::vector<TreeNode*> stack;

        TreeNode* last_node = nullptr;

        while (!stack.empty() || root) {
            if (root) {
                stack.push_back(root);
                root = root->left;
            } else {
                if (stack.back()->right == nullptr || stack.back()->right == last_node) {
                    visited.push_back(stack.back()->val);
                    last_node = stack.back();
                    stack.pop_back();
                } else {
                    root = stack.back()->right;
                }
            }
        }

        return visited;
    }

private:
    void traverse_postorder(TreeNode* root, std::vector<int>& visited)
    {
        if (root == nullptr)
            return;
        traverse_postorder(root->left, visited);
        traverse_postorder(root->right, visited);
        visited.push_back(root->val);
    }
};
